package com.tgy.programmer_code_interview_guide._04_recursion_dynamicProgramming;

import java.util.Arrays;

public class _01_斐波拉契数_matrix {

    public static int fib(int n) {

        /**
         *
         * 已知: f(1) = 1,f(2) = 1, f(3) = 2, f(4)=3
         * (f(n),f(n-1))  = (f(n-1),f(n-2))A
         * A = {
         *     {1,1}
         *     (1,0)
         * }
         *
         *  (f(3),f(2)) = (f(2),f(1))A(3 - 2)
         *
         *  (f(n),f(n-1)) = (f(2),f(1)) A^(n-2)
         */

        if (n <= 2) {

            return 1;
        }

        int top = n - 2;
        int[][] matrix = {{1,1},{1,0}};
        // 初始化为单位矩阵
        int[][] tmpMatrix = {{1,0},{0,1}};
        int index = 1;

        while (index <= top) {

            if ((top & index) != 0) {

                tmpMatrix = matrixMulti(tmpMatrix,matrix);
            }

            index  = (index << 1);
            matrix = matrixMulti(matrix,matrix);
        }

        int[][] pre = {{1,1}};
        int[][] res = matrixMulti(pre,tmpMatrix);
        return res[0][0];
    }

    private static int[][] matrixMulti(int[][] one, int[][] two) {

        int[][] res = new int[one.length][two[0].length];
        for (int i = 0; i < one.length; i++) {

            for (int j = 0; j < two[0].length; j++) {


                for (int k = 0; k < one[0].length; k++) {

                    res[i][j] += (one[i][k] * two[k][j]);
                }
            }
        }

        return res;
    }



    public static void main(String[] args) {

//        int[][] one = {{1,2,3},{3,1,2}};
//        int[][] two = {{1,2},{1,1},{2,2}};
//
//        int[][] res = matrixMulti(one, two);
//
//        for (int i = 0; i < res.length; i++) {
//
//            System.out.println(Arrays.toString(res[i]));
//        }

        /**
         *
         * 1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765
         */
//        for (int i = 1; i <= 20; i++) {
//            int res = fib(i);
//            System.out.println(res);
//        }
        long start = System.currentTimeMillis();
        System.out.println(fib(45));
        // 1134903170
        System.out.println(System.currentTimeMillis() - start);
    }

}
